In recent years, research in a communication field for example, for mobile communication, deep space communication and so forth or a broadcasting field for ground wave broadcasting, satellite digital broadcasting and so forth is being advanced remarkably. Together with this, also research relating to coding theories is being advanced energetically in order to achieve improvement in efficiency in error correct on coding and decoding.
As a theoretical limit to the code performance, the Shannon limit given by the channel coding theory of Shannon (C. E. Shannon) is known. Research relating to the coding theory is performed in order to develop a code which indicates a performance proximate to the Shannon limit. In recent years, as a coding method which indicates a performance proximate to the Shannon limit, a technique called turbo coding (Turbo coding) such as, for example, parallelly concatenated convolutional coding (PCCC (Parallel Concatenated Convolutional Codes)) or serially concatenated convolutional coding (SCCC (Serially Concatenated Convolutional Codes)) has been developed. Further, while those turbo coding methods are developed, low density parity check coding (Low Density Parity Check Codes) (such a code is hereinafter referred to as LDPC code) which is a coding method known for long time is being placed into the spotlight.
An LDPC code was proposed first in Non-Patent Document 1 by R. G. Gallager, and thereafter attracted attention again in Non-Patent Document 2, Non-Patent Document 3 and so forth.
It is becoming clear by research in recent years that, as well as the turbo codes and so on, with the LDPC code, a performance proximate to the Shannon limit is obtained by increasing the code length. Further, since the LDPC code has a nature that the minimum distance increases in proportion to the code length, the LDPC code has a characteristic that it is good in block error probability property and is advantageous also in that an error floor phenomenon which is observed in a decoding property of the turbo coding and so forth little occurs.
In the following, such an LDPC code as described above are described more particularly. It is to be noted that, although the LDPC code is a linear code and need not necessarily be two-dimensional codes, the following description is given on the assumption that the LDPC code is a two-dimensional code.
The LDPC code has the most significant characteristic in that a check matrix (parity check matrix) which defines the LDPC code is sparse. Here, a sparse matrix is a matrix wherein the number of “1s” in the components is very small. If a sparse check matrix is represented by H, then such a check matrix H as just described may be a matrix wherein, for example, as seen in FIG. 1, the Hamming weight (number of “1s”) (weight) of each column is “3” and the Hamming weight of each row is “6” or the like.
An LDPC code defined by a check matrix H wherein the Hamming weight of the rows and the columns is fixed in this manner is called regular LDPC code. Meanwhile, an LDPC code defined by a check matrix H wherein the Hamming weight of the rows and the columns is not fixed are called irregular LDPC codes.
Coding into such an LDPC code is implemented by generating a generator matrix G based on a check matrix H and multiplying the generator matrix G by two-dimensional information word i to generate a codeword. More particularly, a coding apparatus for coding into an LDPC code first calculates a generator matrix G which satisfies an expression GHT=0 with regard to a transposed matrix HT of a check matrix H. Here, where the generator matrix G is a k×n matrix (matrix of k rows and n columns), the check matrix H is a matrix of n−k rows and n columns.
It is to be noted that, for example, in the case of an organization code wherein a codeword c of n bits coincides with a bit string wherein a parity bit p of n−k bits is disposed following an information word i of k bits, where a portion of n−k rows and k columns corresponding to the information word i of k bits from within the codeword c of n bits in a check matrix H of n−k rows and k columns is called information part and another portion of n−k rows and n−k columns corresponding to the parity bit p of n−k bits is called parity part, coding of the information word i into an LDPC code can be performed using the check matrix H if the parity part is an upper triangle code or a lower triangle code.
In particular, if it is assumed that, for example, as shown in FIG. 2, the check matrix H is formed from a parity part of a lower triangle matrix and all of the components of the lower triangle portion of the parity part are 1, then the zeroth bit of the parity bit p of the codeword c exhibits a value obtained by arithmetic operation of EXOR (exclusive ORing) of bits which correspond to those elements which have the value 1 in the zeroth row of the information part of the check matrix H in the information word i.
Further, the first bit of the parity bit p of the codeword c has a value obtained by arithmetic operation of EXOR of bits corresponding to those elements which have the value 1 in the first row of the information part of the check matrix H of the information word i and the zeroth bit of the parity bit p.
Further, the second bit of the parity bit p of the codeword c has a value obtained by arithmetic operation of EXOR of those bits which have the value 1 in the second row of the information part of the check matrix H of the information word i and the zeroth bit and the first bit of the parity bit p.
Similarly, the mth bit of the parity bit p of the codeword c has a value obtained by arithmetic operation of EXOR of those bits which have the value 1 in the mth row of the information part of the check matrix H of the information word i and the zeroth to m−1th bits of the parity bit p.
The codeword c of n bits can be obtained by determining the parity bit p of n−k bits and disposing the determined parity bit p following the information word i of k bits in such a manner as described above.
In particular, if a check matrix H whose parity part is a lower triangle matrix is generalized as seen in FIG. 3, then coding of the Information word i into an LDPC code is performed in the following manner using the check matrix H.
In FIG. 3, the components of the zeroth row (uppermost row) of the check matrix H include h0,0, h0,1, . . . , h0,k-1 in the information part and 1, 0, . . . , 0 in the parity part in order from the zeroth column (leftmost column). Meanwhile, the components of the first row include h1,0, h1,1, . . . , h1,k-1 in the information part and h1,k, 1, . . . , 0 in the parity part in order from the zeroth column. Similarly, the components of the n−k−1th row (lowermost row) include hn-k-1,0, hn-k-1,1, . . . , hn-k-1,k-1 in the information part and hn-k-1,k, . . . , hn-k-1,n-2, 1 in the parity part in order from the zeroth column.
Here, the information word i of k bits is represented as i0, i1, . . . , ik-1 and the parity bit p of n−k bits are represented as p0, p1, . . . , pn-k-1. In other words, the codeword c is represented as i0, i1, . . . , ik-1, p0, p1, . . . , pn-k-1. Since the exclusive OR of the products of the codeword c and the rows of the check matrix H is 0, arithmetic operation of the products of the codeword c and the zeroth row of the check matrix H is represented by the following expression (1).
[Expression 1]h0,0i0+h0,1i1+ . . . +h0,k-1ik-1+p0=0(mod 2)  (1)
Accordingly, the parity bit p0 is represented by the following expression (2).
                    [                  Expression          ⁢                                          ⁢          2                ]                                                                      p          0                =                              ∑                          j              =              0                                      k              -              1                                ⁢                                          ⁢                                    h                              0                ,                j                                      ⁢                          i              j                        ⁢                                                  ⁢                          (                              mod                ⁢                                                                  ⁢                2                            )                                                          (        2        )            
Arithmetic operation of the product of the codeword c and the first row of the check matrix H is represented by the following expression (3).
[Expression 3]h1,0i0+h1,1i1+ . . . +h1,k-1ik-1+h1,kp0+p1=0(mod 2)  (3)
Accordingly, the parity bit p1 is represented by the following expression (4).
                    [                  Expression          ⁢                                          ⁢          4                ]                                                                      p          1                =                                            ∑                              j                =                0                                            k                -                1                                      ⁢                                          h                                  1                  ,                  j                                            ⁢                              i                j                                              +                                    h                              1                ,                k                                      ⁢                          p              0                        ⁢                                                  ⁢                          (                              mod                ⁢                                                                  ⁢                2                            )                                                          (        4        )            
Similarly, the arithmetic operation of the product of the codeword c and the n−k−1th row of the check matrix H is represented by the following expression (5):
[Expression 5]hn-k-1,0i0+hn-k-1,1i1+ . . . +hn-k-1,k-1ik-1+hn-k-1,kp0+hn-k-1,k+p1+ . . . +hn-k-1,n-k-2pn-k-2+pn-k-1=0(mod 5)  (5)
Accordingly, the parity bit pn-k-1 is represented by the following expression (6).
                    [                  Expression          ⁢                                          ⁢          6                ]                                                                      p                      n            -            k            -            1                          =                                            ∑                              j                =                0                                            k                -                1                                      ⁢                                                  ⁢                                          h                                                      n                    -                    k                    -                    1                                    ,                  j                                            ⁢                              i                j                                              +                                    ∑                              j                =                2                                            n                -                k                -                2                                      ⁢                                                  ⁢                                          h                                                      n                    -                    k                    -                    1                                    ,                                      k                    +                    j                                                              ⁢                              p                j                            ⁢                                                          ⁢                              (                                  mod                  ⁢                                                                          ⁢                  2                                )                                                                        (        6        )            
The codeword c of n bits can be obtained by determining the parity bit p0, p1, . . . , pn-k-1 of n−k bits and disposing the determined parity bit following the information word i0, i1, . . . , ik-1 of k bits in such a manner as described above.
In recent years, research also regarding a mounting method of a coding apparatus for an LDPC code has been and is being carried out, and a method of mounting a coding apparatus using a shift register and a method of mounting a coding apparatus using a RAM (Random Access Memory) in place of a shift register are available.
[Non-Patent Document 1] R. G. Gallager, “Low Density Parity Check Codes”, Cambridge, Mass.: M. I. T. Press, 1963
[Non-Patent Document 2] D. J. C. MacKay, “Good error correcting codes based on very sparse matrices”, Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999
[Non-Patent Document 3] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, “Analysis of low density codes and improved designs using irregular graphs”, Proceedings of the thirtieth annual ACM Symposium on Theory of Computing (STOC), 1998, pp. 249-258